Search for: All records

A great many problems in network information theory, both fundamental and applied, involve determining a minimal set of inequalities linking the Shannon entropies of a certain collection of subsets of random variables. In principle this minimal set of inequalities could be determined from the entropy region, whose dimensions are all the subsets of random variables, by projecting out dimensions corresponding to the irrelevant subsets. As a general solution technique, however, this method is plagued both by the incompletely known nature of the entropy region as well as the exponential complexity of its bounds. Even worse, for four or more random variables, it is known that the set of linear information inequalities necessary to completely describe the entropy region must be uncountably infinite. A natural question arises then, if there are certain nontrivial collections of subsets where the inequalities linking only these subsets is both completely known, and have inequality descriptions that are linear in the number of random variables. This paper answers this question in the affirmative. A decomposition expressing the collection of inequalities linking a larger collection of subsets from that of smaller collections of subsets is first proven. This decomposition is then used to provide systems of subsets for which it both exhaustively determines the complete list of inequalities, which is linear in the number of variables. 

Determining the rate region of a network is of great importance in the research area of network coding. Lots of attempts have been made and significant progress has been achieved over the last decade on this topic. Although these researches provide us with multiple ways of calculating the outer or inner bounds of rate region, the sheer complexity of the problem, which involves expressing and projecting a very high dimensional polyhedra, makes it computationally infeasible beyond networks with 10s of edges. Aimed at reducing the complexity of the rate region calculation, in this paper a new theorem that implicitly determines the rate region of a network is proved and a corresponding systematic way of applying the theorem to calculate explicitly the outer bounds to a rate region is proposed. Compared with the traditional method, the proposed method has the potential to calculate the true rate region via the projection of simpler polyhedra that has exponentially less dimensions and is characterized by exponentially less facets. 

A new method is presented, consisting of exclusively simple linear algebra computations, for computing the linear programming Shannon outer bound to the network coding capacity region of a directed hypergraph network. This linear algebraic formulation enables a new upper bound on the worst case complexity of computing the Shannon outer bound to a network coding capacity region to be determined. 

The boundary of the entropy region has been shown to determine fundamental inequalities and limits in key problems in network coding, streaming, distributed storage, and coded caching. The unknown part of this boundary requires nonlinear constructions, which can, in turn, be parameterized by the support of their underlying probability distributions. Recognizing that the terms in entropy are submodular enables the design of such supports to maximally push out towards this boundary.